package leetcode.code0060;

public class Solution extends Solution60 {

	public static int[] table = new int[10];// 各阶数值

	static {
		table[0] = 1;
		for (int i = 1; i < 10; i++) {
			table[i] = table[i - 1] * i;
		}
	}

	@Override
	public String getPermutation(int n, int k) {
		boolean[] used = new boolean[10];// 记录数字是否被使用
		char[] ans = new char[n];// 答案
		for (int i = 1; i <= n; i++) {//从左往右,第i位数上
			// div决定了当前位是未用数字中的第几小,0是第一小,也就是最小 ; 1是第二小 ...
			// k==0 是这组最后一个数, div = n-i, k只有在%下一组每组数量时候会是0, 说明他是下一组的最后一个
			// k!=0 时, 如果(k % table[n - i]) == 0 ,div是上一组最后一个, div = k / table[n - i] - 1
			// k!=0 && (k % table[n - i]) != 0 时,div = k / table[n - i]
			int div = k == 0 ? n - i : (k % table[n - i]) == 0 ? k / table[n - i] - 1 : k / table[n - i];// 使得边界落在上一组,当前位是第div小
			k %= table[n - i];// 降一位
			// 找到当前位数字
			for (int j = 1; j <= n; j++) {// 取未用数据中,第div+1小,0是第一小,也就是最小 ; 1是第二小 ...
				if (!used[j]) {
					if (div == 0) {
						ans[i - 1] = (char) (j + '0');
						used[j] = true;// 第div+1小 就是这一位答案
						break;
					} else {
						div--;
					}
				}
			}
		}
		return new String(ans);
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
